package com.zhaofan.offer;

import com.algo.tree.BinaryTree;
import org.junit.Test;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Objects;

/**
 * https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
 */
public class No68 {

    @Test
    public void test() {
        Integer[] a = {3, 5, 1, 6, 2, 0, 8, null, null, 7, 4};
        TreeNode root = builderTree(a);
        TreeNode v5 = new TreeNode(5);
        TreeNode v1 = new TreeNode(1);
        TreeNode treeNode = lowestCommonAncestor(root, v1, v5);
        System.out.println(treeNode.val);
    }

    public TreeNode builderTree(Integer[] a) {
        if (a.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(a[0]);
        TreeNode tmp;
        LinkedList<TreeNode> list = new LinkedList<>();
        list.offer(root);
        for (int i = 1; i < a.length; i++) {
            if (i % 2 == 1) {
                tmp = list.peek();
                TreeNode left;
                if (a[i] == null) {
                    left = null;
                } else {
                    left = new TreeNode(a[i]);
                }
                tmp.left = left;
                list.offer(left);
            } else {
                tmp = list.poll();
                TreeNode right;
                if (a[i] == null) {
                    right = null;
                } else {
                    right = new TreeNode(a[i]);
                }
                tmp.right = right;
                list.offer(right);
            }
        }
        return root;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        HashMap<TreeNode, TreeNode> map = getTreeMap(root, p, q);
        TreeNode tmp = p;
        ArrayList<TreeNode> list = new ArrayList<>();
        list.add(p);
        while (true) {
            tmp = map.get(tmp);
            if (tmp == null) {
                break;
            } else {
                list.add(tmp);
            }
        }

        if (list.contains(q)) {
            return q;
        }

        tmp = q;
        while (true) {
            tmp = map.get(tmp);
            if (list.contains(tmp)) {
                return tmp;
            }
        }
    }

    //遍历树,返回值为key：子节点，value：父节点
    public HashMap<TreeNode, TreeNode> getTreeMap(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        HashMap<TreeNode, TreeNode> store = new HashMap<>();
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        while (!list.isEmpty() && (!store.containsKey(p) || !store.containsKey(q))) {
            TreeNode node = list.poll();
            if (node.left != null) {
                list.offer(node.left);
                store.put(node.left, node);
            }
            if (node.right != null) {
                list.offer(node.right);
                store.put(node.right, node);
            }
        }
        return store;
    }


    public class TreeNode {
        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode() {
        }

        int val;

        TreeNode left;

        TreeNode right;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            TreeNode treeNode = (TreeNode) o;
            return Objects.equals(val, treeNode.val);
        }

        @Override
        public int hashCode() {
            return Objects.hash(val);
        }
    }

    public int[] test1(int[] a, int[] b) {
        if (a == null || b == null) {
            throw new NullPointerException("数组为null");
        } else if (a.length == 0) {
            return b;
        } else if (b.length == 0) {
            return a;
        }
        int[] c = new int[a.length + b.length];
        int i = 0, j = 0, p = 0;
        while (i < a.length && j < b.length) {
            if (a[i] <= b[j]) {
                c[p++] = a[i++];
            } else {
                c[p++] = b[j++];
            }
        }
        while (i == a.length && j < b.length) {
            c[p++] = b[j++];
        }
        while (i < a.length && j == b.length) {
            c[p++] = a[i++];
        }
        return c;
    }
}